촐레스키 분해

작성자

익명

작성일

2026.07.29

조회수

버전

촐레스키 분해 (Cholesky Decomposition)

1. 개요

촐레스키 분해란 실수 행렬의 경우 대칭 행렬(Symmetric matrix)이자 양의 정부호 행렬(Positive-definite matrix)인 행렬 $A$를 하삼각행렬(Lower triangular matrix) $L$과 그 전치행렬 $L^T$의 곱으로 분해하는 행렬 분해 기법이다. 수학적으로는 다음과 같이 정의된다.

$$A = LL^T$$

여기서 $L$은 대각 성분이 모두 양수인 하삼각행렬이다. 이는 일반적인 LU 분해의 특수한 형태로, 행렬의 대칭성을 이용하여 계산 효율성을 극대화한 방법이다.

2. 성립 조건

촐레스키 분해가 가능하기 위해서는 대상 행렬 $A$가 반드시 다음의 두 가지 조건을 동시에 만족해야 한다.

대칭 행렬 (Symmetric Matrix): $A = A^T$를 만족해야 한다. 즉, 주대각선을 기준으로 원소들이 대칭적이어야 한다.
양의 정부호 행렬 (Positive-definite Matrix): 0이 아닌 모든 벡터 $x$에 대하여 $x^T Ax > 0$을 만족해야 한다. 이는 모든 고윳값(Eigenvalue)이 양수임을 의미한다.

참고로, 양의 준정부호 행렬(Positive semi-definite matrix)의 경우 대각 성분이 0이 될 수 있어 일반적인 촐레스키 분해는 불가능하지만, 피보팅을 통한 분해는 가능하다.

[표 1] 일반 행렬 분해와 촐레스키 분해의 조건 비교

구분	LU 분해	촐레스키 분해
대상 행렬	정방행렬 (일반적)	대칭 및 양의 정부호 행렬
분해 형태	$A = LU$	$A = LL^T$
제약 조건	주소행렬(Principal Minor) $\neq 0$	모든 고윳값 $> 0$
특징	범용적이나 계산량이 많음	조건 충족 시 매우 빠르고 안정적임

3. 계산 원리 및 알고리즘

촐레스키 분해는 행렬 $A$의 원소 $a_{ij}$와 하삼각행렬 $L$의 원소 $l_{ij}$ 사이의 관계식을 통해 재귀적으로 계산한다.

3.1. 수학적 유도 (Cholesky-Banachiewicz 알고리즘)

$A = LL^T$의 각 원소를 전개하면 다음과 같은 공식을 얻을 수 있다.

대각 성분 ($i = j$): $$l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2}$$
비대각 성분 ($i > j$): $$l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk} \right)$$

3.2. 계산 복잡도

촐레스키 분해의 연산량은 약 $\frac{1}{3}n^3$ 플롭스(FLOPs)로, 일반적인 LU 분해($\frac{2}{3}n^3$)보다 약 2배 더 효율적이다. 이는 대칭성을 이용하여 계산량을 절반으로 줄였기 때문이다.

3.3. Python 구현 예시

직접 알고리즘을 구현하는 방법과 NumPy 라이브러리를 사용하는 방법이 있다.

직접 구현 (알고리즘 학습용)

import numpy as np

def cholesky_decomposition(A):
    n = A.shape[0]
    L = np.zeros_like(A)

    for i in range(n):
        for j in range(i + 1):
            # NumPy 벡터 연산을 사용하여 효율적으로 계산
            s = np.dot(L[i, :j], L[j, :j])
            if i == j:
                L[i][j] = np.sqrt(A[i][i] - s)
            else:
                L[i][j] = (1.0 / L[j][j] * (A[i][j] - s))
    return L

# 테스트 행렬 (대칭 및 양의 정부호)
A = np.array([[4, 12, -16], 
              [12, 37, -43], 
              [-16, -43, 98]], dtype=float)
print(cholesky_decomposition(A))

NumPy 라이브러리 사용 (실무용)

실제 프로젝트에서는 최적화된 np.linalg.cholesky 함수를 사용하는 것이 권장된다.

import numpy as np

A = np.array([[4, 12, -16], 
              [12, 37, -43], 
              [-16, -43, 98]], dtype=float)

L = np.linalg.cholesky(A)
print(L)

4. 단계별 계산 예제 (3x3 행렬)

다음 행렬 $A$를 촐레스키 분해하는 과정은 다음과 같다. $$A = \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix}$$

1열 계산:
$l_{11} = \sqrt{a_{11}} = \sqrt{4} = \mathbf{2}$
$l_{21} = a_{21} / l_{11} = 12 / 2 = \mathbf{6}$
$l_{31} = a_{31} / l_{11} = -16 / 2 = \mathbf{-8}$
2열 계산:
$l_{22} = \sqrt{a_{22} - l_{21}^2} = \sqrt{37 - 6^2} = \sqrt{1} = \mathbf{1}$
$l_{32} = (a_{32} - l_{31}l_{21}) / l_{22} = (-43 - (-8 \times 6)) / 1 = (-43 + 48) / 1 = \mathbf{5}$
3열 계산:
$l_{33} = \sqrt{a_{33} - (l_{31}^2 + l_{32}^2)} = \sqrt{98 - ((-8)^2 + 5^2)} = \sqrt{98 - (64 + 25)} = \sqrt{9} = \mathbf{3}$

최종 결과: $$L = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix} = \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 5 & 3 \end{pmatrix}$$

5. 수치적 안정성 및 피보팅

촐레스키 분해는 수치적으로 매우 안정적인 알고리즘으로 알려져 있다.

피보팅(Pivoting) 불필요: 일반적인 LU 분해에서는 0으로 나누는 것을 방지하거나 오차를 줄이기 위해 행을 교환하는 피보팅 과정이 필수적이다. 그러나 양의 정부호 행렬에 대한 촐레스키 분해는 피보팅 없이도 수치적 안정성이 보장된다.
오차 전파: 대각 성분이 매우 작을 경우 수치적 불안정성이 발생할 수 있으나, 이는 행렬이 '양의 준정부호(Positive semi-definite)'에 가까워질 때 발생하는 문제이다. 이 경우 피보팅 촐레스키 분해(Pivoted Cholesky)를 사용하여 가장 큰 대각 원소를 선택함으로써 수치적 안정성을 높이고 랭크 부족(Rank-deficient) 문제를 해결할 수 있다.

6. 주요 활용 사례

$Ax = b$를 $LL^T x = b$로 변환하여 두 단계로 해결한다. 1. 전방 대입(Forward Substitution): $Ly = b$를 풀어 $y$를 구한다. 2. 후방 대입(Backward Substitution): $L^T x = y$를 풀어 $x$를 구한다. 이 과정은 $O(n^2)$의 복잡도로 매우 빠르게 수행되며, 특히 $A$가 고정되고 $b$만 변하는 여러 개의 방정식을 풀 때 매우 효율적이다.

6.2. 다변량 정규분포 난수 생성

상관관계 행렬 $\Sigma$가 주어졌을 때, 촐레스키 분해 $\Sigma = LL^T$를 이용하면 독립적인 표준정규분포 벡터 $z \sim N(0, I)$를 사용하여 상관관계가 있는 난수 $x$를 생성할 수 있다. $$x = \mu + Lz$$

6.3. 기타 활용

최소제곱법 (Least Squares): 정규 방정식 $A^T Ax = A^T b$에서 $A^T A$는 항상 대칭 및 양의 준정부호 행렬이므로 촐레스키 분해가 효율적으로 사용된다.
칼만 필터 (Kalman Filter): 공분산 행렬의 업데이트 및 수치적 안정성 확보를 위해 사용된다.

7. 비교 분석: LU 분해 및 LDL 분해

7.1. LU 분해와의 비교

촐레스키 분해는 LU 분해의 특수한 케이스이다. $A = LU$에서 $U = L^T$가 되는 조건이 바로 대칭 양의 정부호 행렬인 경우이다.

[표 2] LU 분해 vs 촐레스키 분해

항목	LU 분해	촐레스키 분해
계산 속도	보통 ($\frac{2}{3}n^3$)	매우 빠름 ($\frac{1}{3}n^3$)
메모리 사용	$L, U$ 두 행렬 저장 필요	$L$ 하나만 저장 가능 (절반)
안정성	피보팅 필요	피보팅 없이 안정적

7.2. LDL 분해와의 차이점

LDL 분해는 $A = LDL^T$ 형태로 분해하는 방법으로, $D$는 대각행렬이다. - 제곱근 연산: 촐레스키 분해는 $\sqrt{\cdot}$ 연산이 필요하지만, LDL 분해는 제곱근 연산이 필요 없다. - 적용 범위: 촐레스키 분해는 반드시 '양의 정부호'여야 하지만, LDL 분해는 '대칭 행렬'이기만 하면(음의 고윳값이 있어도) 가능하다. - 효율성: 제곱근 연산 비용을 줄여야 하는 임베디드 시스템 등에서는 LDL 분해가 더 선호된다.

분류: 수학 / 선형대수학 / 행렬 분해

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 촐레스키 분해 (Cholesky Decomposition)

## 1. 개요
**촐레스키 분해**란 실수 행렬의 경우 **대칭 행렬(Symmetric matrix)**이자 양의 정부호 행렬(Positive-definite matrix)인 행렬 $A$를 하삼각행렬(Lower triangular matrix) $L$과 그 전치행렬 $L^T$의 곱으로 분해하는 행렬 분해 기법이다. 수학적으로는 다음과 같이 정의된다.

$$A = LL^T$$

여기서 $L$은 대각 성분이 모두 양수인 하삼각행렬이다. 이는 일반적인 LU 분해의 특수한 형태로, 행렬의 대칭성을 이용하여 계산 효율성을 극대화한 방법이다.

## 2. 성립 조건
촐레스키 분해가 가능하기 위해서는 대상 행렬 $A$가 반드시 다음의 두 가지 조건을 동시에 만족해야 한다.

1. **대칭 행렬 (Symmetric Matrix):** $A = A^T$를 만족해야 한다. 즉, 주대각선을 기준으로 원소들이 대칭적이어야 한다.
2. **양의 정부호 행렬 (Positive-definite Matrix):** 0이 아닌 모든 벡터 $x$에 대하여 $x^T Ax > 0$을 만족해야 한다. 이는 모든 고윳값(Eigenvalue)이 양수임을 의미한다.

참고로, **양의 준정부호 행렬(Positive semi-definite matrix)**의 경우 대각 성분이 0이 될 수 있어 일반적인 촐레스키 분해는 불가능하지만, 피보팅을 통한 분해는 가능하다.

### [표 1] 일반 행렬 분해와 촐레스키 분해의 조건 비교

| 구분 | LU 분해 | 촐레스키 분해 |
| :--- | :--- | :--- |
| **대상 행렬** | 정방행렬 (일반적) | 대칭 및 양의 정부호 행렬 |
| **분해 형태** | $A = LU$ | $A = LL^T$ |
| **제약 조건** | 주소행렬(Principal Minor) $\neq 0$ | 모든 고윳값 $> 0$ |
| **특징** | 범용적이나 계산량이 많음 | 조건 충족 시 매우 빠르고 안정적임 |

## 3. 계산 원리 및 알고리즘
촐레스키 분해는 행렬 $A$의 원소 $a_{ij}$와 하삼각행렬 $L$의 원소 $l_{ij}$ 사이의 관계식을 통해 재귀적으로 계산한다.

### 3.1. 수학적 유도 (Cholesky-Banachiewicz 알고리즘)
$A = LL^T$의 각 원소를 전개하면 다음과 같은 공식을 얻을 수 있다.

- **대각 성분 ($i = j$):**
  $$l_{ii} = \sqrt{a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2}$$
- **비대각 성분 ($i > j$):**
  $$l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik}l_{jk} \right)$$

### 3.2. 계산 복잡도
촐레스키 분해의 연산량은 약 $\frac{1}{3}n^3$ 플롭스(FLOPs)로, 일반적인 LU 분해($\frac{2}{3}n^3$)보다 약 2배 더 효율적이다. 이는 대칭성을 이용하여 계산량을 절반으로 줄였기 때문이다.

### 3.3. Python 구현 예시
직접 알고리즘을 구현하는 방법과 NumPy 라이브러리를 사용하는 방법이 있다.

#### 직접 구현 (알고리즘 학습용)
```python
import numpy as np

def cholesky_decomposition(A):
    n = A.shape[0]
    L = np.zeros_like(A)

    for i in range(n):
        for j in range(i + 1):
            # NumPy 벡터 연산을 사용하여 효율적으로 계산
            s = np.dot(L[i, :j], L[j, :j])
            if i == j:
                L[i][j] = np.sqrt(A[i][i] - s)
            else:
                L[i][j] = (1.0 / L[j][j] * (A[i][j] - s))
    return L

# 테스트 행렬 (대칭 및 양의 정부호)
A = np.array([[4, 12, -16], 
              [12, 37, -43], 
              [-16, -43, 98]], dtype=float)
print(cholesky_decomposition(A))
```

#### NumPy 라이브러리 사용 (실무용)
실제 프로젝트에서는 최적화된 `np.linalg.cholesky` 함수를 사용하는 것이 권장된다.
```python
import numpy as np

A = np.array([[4, 12, -16], 
              [12, 37, -43], 
              [-16, -43, 98]], dtype=float)

L = np.linalg.cholesky(A)
print(L)
```

## 4. 단계별 계산 예제 (3x3 행렬)
다음 행렬 $A$를 촐레스키 분해하는 과정은 다음과 같다.
$$A = \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix}$$

1. **1열 계산:**
   - $l_{11} = \sqrt{a_{11}} = \sqrt{4} = \mathbf{2}$
   - $l_{21} = a_{21} / l_{11} = 12 / 2 = \mathbf{6}$
   - $l_{31} = a_{31} / l_{11} = -16 / 2 = \mathbf{-8}$

2. **2열 계산:**
   - $l_{22} = \sqrt{a_{22} - l_{21}^2} = \sqrt{37 - 6^2} = \sqrt{1} = \mathbf{1}$
   - $l_{32} = (a_{32} - l_{31}l_{21}) / l_{22} = (-43 - (-8 \times 6)) / 1 = (-43 + 48) / 1 = \mathbf{5}$

3. **3열 계산:**
   - $l_{33} = \sqrt{a_{33} - (l_{31}^2 + l_{32}^2)} = \sqrt{98 - ((-8)^2 + 5^2)} = \sqrt{98 - (64 + 25)} = \sqrt{9} = \mathbf{3}$

**최종 결과:**
$$L = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix} = \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 5 & 3 \end{pmatrix}$$

## 5. 수치적 안정성 및 피보팅
촐레스키 분해는 수치적으로 매우 안정적인 알고리즘으로 알려져 있다.

- **피보팅(Pivoting) 불필요:** 일반적인 LU 분해에서는 0으로 나누는 것을 방지하거나 오차를 줄이기 위해 행을 교환하는 피보팅 과정이 필수적이다. 그러나 양의 정부호 행렬에 대한 촐레스키 분해는 피보팅 없이도 수치적 안정성이 보장된다.
- **오차 전파:** 대각 성분이 매우 작을 경우 수치적 불안정성이 발생할 수 있으나, 이는 행렬이 '양의 준정부호(Positive semi-definite)'에 가까워질 때 발생하는 문제이다. 이 경우 **피보팅 촐레스키 분해(Pivoted Cholesky)**를 사용하여 가장 큰 대각 원소를 선택함으로써 수치적 안정성을 높이고 랭크 부족(Rank-deficient) 문제를 해결할 수 있다.

## 6. 주요 활용 사례
### 6.1. 선형 연립방정식 풀이
$Ax = b$를 $LL^T x = b$로 변환하여 두 단계로 해결한다.
1. **전방 대입(Forward Substitution):** $Ly = b$를 풀어 $y$를 구한다.
2. **후방 대입(Backward Substitution):** $L^T x = y$를 풀어 $x$를 구한다.
이 과정은 $O(n^2)$의 복잡도로 매우 빠르게 수행되며, 특히 $A$가 고정되고 $b$만 변하는 여러 개의 방정식을 풀 때 매우 효율적이다.

### 6.2. 다변량 정규분포 난수 생성
상관관계 행렬 $\Sigma$가 주어졌을 때, 촐레스키 분해 $\Sigma = LL^T$를 이용하면 독립적인 표준정규분포 벡터 $z \sim N(0, I)$를 사용하여 상관관계가 있는 난수 $x$를 생성할 수 있다.
$$x = \mu + Lz$$

### 6.3. 기타 활용
- **최소제곱법 (Least Squares):** 정규 방정식 $A^T Ax = A^T b$에서 $A^T A$는 항상 대칭 및 양의 준정부호 행렬이므로 촐레스키 분해가 효율적으로 사용된다.
- **칼만 필터 (Kalman Filter):** 공분산 행렬의 업데이트 및 수치적 안정성 확보를 위해 사용된다.

## 7. 비교 분석: LU 분해 및 LDL 분해

### 7.1. LU 분해와의 비교
촐레스키 분해는 LU 분해의 특수한 케이스이다. $A = LU$에서 $U = L^T$가 되는 조건이 바로 대칭 양의 정부호 행렬인 경우이다.

### [표 2] LU 분해 vs 촐레스키 분해

| 항목 | LU 분해 | 촐레스키 분해 |
| :--- | :--- | :--- |
| **계산 속도** | 보통 ($\frac{2}{3}n^3$) | 매우 빠름 ($\frac{1}{3}n^3$) |
| **메모리 사용** | $L, U$ 두 행렬 저장 필요 | $L$ 하나만 저장 가능 (절반) |
| **안정성** | 피보팅 필요 | 피보팅 없이 안정적 |

### 7.2. LDL 분해와의 차이점
**LDL 분해**는 $A = LDL^T$ 형태로 분해하는 방법으로, $D$는 대각행렬이다.
- **제곱근 연산:** 촐레스키 분해는 $\sqrt{\cdot}$ 연산이 필요하지만, LDL 분해는 제곱근 연산이 필요 없다.
- **적용 범위:** 촐레스키 분해는 반드시 '양의 정부호'여야 하지만, LDL 분해는 '대칭 행렬'이기만 하면(음의 고윳값이 있어도) 가능하다.
- **효율성:** 제곱근 연산 비용을 줄여야 하는 임베디드 시스템 등에서는 LDL 분해가 더 선호된다.

분류: 수학 / 선형대수학 / 행렬 분해

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나